#!/usr/bin/env python
#
# Type checker for the Simple LISP Dialect for Teaching
#
# Author:   Mike Murphy <mamurph@cs.clemson.edu>
# Revision: 17 January 2009
#
# Copyright 2008-2009 Clemson University
#
# Permission is hereby granted, free of charge, to any person obtaining a
# copy of this software and associated documentation files (the "Software"),
# to deal in the Software without restriction, including without limitation
# the rights to use, copy, modify, merge, publish, distribute, sublicense,
# and/or sell copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
# IN THE SOFTWARE.
#
# This material is based upon work supported under a National Science
# Foundation Graduate Research Fellowship. Any opinions, findings,
# conclusions or recommendations expressed in this publication are those of
# the author(s) and do not necessarily reflect the views of the National
# Science Foundation.

import sys
from shared_config import OPERATOR_LIST, SCAN_TYPES, CompilerException
from stack_model import StackModel

# Controls debug/trace messages *for this module only*
DEBUG=False
TRACE=False


# Debug and trace routines
def dbg(msg):
   if DEBUG:
      print >> sys.stderr, '*TC:DEBUG*:', msg
#

def trace(msg):
   if TRACE:
      print >> sys.stderr, '*TC:TRACE*:', msg
#


# Custom exception for type-checker errors
class TypeCheckerException(CompilerException):
   def __init__(self, message, line):
      CompilerException.__init__(self, 'Type Error: ' + str(message), line)
#


# ControlHandler class: implements logic for dealing with @define control
# statements
class ControlHandler(object):
   def __init__(self, symbol_table):
      self.symbol_table = symbol_table
      self.control_map = { 'define' : self.handle_define }
   def handle_define(self, name_tok, val_tok):
      trace('enter handle_define')
      raw_value = None
      dbg('val_tok[0] == %s' % val_tok[0])
      if val_tok[0] == SCAN_TYPES['NAME']:
         name = val_tok[1]
         dbg('performing symbol table lookup on %s' % name)
         if name in self.symbol_table:
            raw_value = self.symbol_table[name]
         else:
            trace('leave handle_define by exception')
            raise TypeCheckerException('not in symbol table: ' + name, \
                                       val_tok[2])
      elif val_tok[0] == SCAN_TYPES['INT']:
         raw_value = val_tok[1]
      else:
         trace('leave handle_define by exception')
         raise Exception('BUG: in ControlHandler.handle_define')
      #
      symname = name_tok[1]
      dbg('requested new symbol: %s with value %s' % (symname, str(raw_value)))
      dbg('symbol table is: %s' % str(self.symbol_table))
      if symname not in self.symbol_table:
         self.symbol_table[symname] = raw_value
      else:
         trace('leave handle_define by exception')
         raise TypeCheckerException('attempted re-declaration of symbol: ' + \
                                    symname, name_tok[2])
      #
      trace('leave handle_define')
   def handle_control(self, subtree):
      trace('enter handle_control')
      control_tok = subtree[0]
      name_tok = subtree[1]
      val_tok = subtree[2]
      dbg('control token: %s' % str(control_tok))
      dbg('name token: %s' % str(name_tok))
      dbg('value token: %s' % str(val_tok))
      control_name = control_tok[1]
      dbg('control name: %s' % control_name)
      dbg('control map: %s' % str(self.control_map))
      if control_name in self.control_map:
         self.control_map[control_name](name_tok, val_tok)
      else:
         trace('leave handle_control by exception')
         raise TypeCheckerException('invalid control token: ' + control_name,
                                    control_tok[2])
      #
      trace('leave handle_control')
#


# Actual type-checker
class TypeChecker(object):
   def __init__(self, parser, symbol_table):
      self.parser = parser
      self.stack = StackModel()
      self.symbol_table = symbol_table
      self.control_handler = ControlHandler(self.symbol_table)
      # Result of type-checking is a final tree that has been pruned of
      # control statements and is known to be "good" in SLDT terms
      self.final_tree = []
   def check_statement(self, tree, is_outermost = False):
      '''Checks a single SLDT statement, represented by a tree'''
      trace('enter check_statement')
      dbg('tree is: %s' % str(tree))
      dbg('outermost? %s' % str(is_outermost))
      op = tree[0]
      argct = len(tree) - 1
      dbg('operator: %s argument count: %d' % (op, argct))
      for subtree in tree[1:]:
         if isinstance(subtree, list):   # subtree is an actual tree
            dbg('making recursive call with subtree: %s' % str(subtree))
            self.check_statement(subtree)
         elif isinstance(subtree, tuple):   # subtree is a token
            toktype = subtree[0]
            dbg('argument toktype is: %s' % toktype)
            if toktype == SCAN_TYPES['INT']:
               self.stack.push()   # Know we have an int
            elif toktype == SCAN_TYPES['NAME']:
               name = subtree[1]
               dbg('checking for name %s in symbol table' % name)
               dbg('symbol table: %s' % self.symbol_table)
               if name in self.symbol_table:
                  # If we had types other than int, would have to check
                  # symbol type. But we only have int, and we know the symbol
                  # is valid
                  self.stack.push()
               else:
                  trace('leave check_statement by exception')
                  raise TypeCheckerException('not in symbol table: ' + name,
                                             subtree[2])
            else:
               trace('leave check_statement by exception')
               raise TypeCheckerException('illegal type in expression: ' + \
                                          str(subtree[1]), subtree[2])
         else:
            trace('leave check_statement by exception')
            raise TypeCheckerException('inconsistent parse tree (check for ' + \
                      'prior errors)', -1)
      #
      # Sanity check before operator lookup
      if isinstance(op, list):
         trace('leave check_statement by exception')
         raise TypeCheckerException('expected operator but got subexpression', \
                                    -1)
      if op[0] != SCAN_TYPES['OPER']:
         trace('leave check_statement by exception')
         raise TypeCheckerException('not an operator: ' + str(op[1]), op[2])
      opname = op[1]
      dbg('checking for operator %s in op map %s' % (opname, OPERATOR_LIST))
      if opname in OPERATOR_LIST:
         min_args, max_args, stack_out, num_local = OPERATOR_LIST[opname]
         dbg('op: %s min args: %d max: %d have: %d stack effect: %d' % \
             (opname, min_args, max_args, argct, stack_out))
         if argct >= min_args and argct <= max_args:
            dbg('operator type-checked: performing stack simulation')
            # Push then immediately consume locals, so that stack can track
            # max size properly
            if num_local > 0:
               dbg('operator uses local stack space: %d' % num_local)
               self.stack.push(num_local)
               self.stack.consume(num_local)
            # Simulate running the operation and make sure stack OK
            chk = self.stack.consume(argct)
            if not chk:
               trace('leave check_statement by exception')
               raise TypeCheckerException('stack underflow: ' + opname, op[2])
            #
            # Push result onto stack
            self.stack.push(stack_out)
         else:
            dbg('operator had incorrect argument count')
            trace('leave check_statement by exception')
            raise TypeCheckerException('bad argument count: ' + opname, op[2])
      else:
         dbg('operator not found')
         trace('leave check_statement by exception')
         raise TypeCheckerException('unknown operator: ' + opname, op[2])
      #
      # If this is an outermost tree, there is an implicit print statement
      # that consumes 1 integer from the stack, leaving the stack empty
      if is_outermost:
         dbg('outermost statement level: simulating print routine')
         dbg('stack size: %d' % self.stack.size)
         # Jasmin print routine first requires a:
         #     getstatic java/lang/System/out Ljava/io/PrintStream;
         # This statement puts 1 extra item on the stack. When println is
         # called with invokevirtual, both items are consumed from the stack.
         self.stack.push(1)
         chk = self.stack.consume(2)
         if not chk:
            trace('leave check_statement by exception')
            raise TypeCheckerException('top-level stack underflow', op[2])
         if not self.stack.isEmpty():
            trace('leave check_statement by exception')
            raise TypeCheckerException('%d orphan(s) left on stack' % \
                                       self.stack.size, op[2])
      #
      # No return: if we didn't throw an exception, life is good
      trace('leave check_statement')
   def convert_empty_subtrees(self, tree):
      '''Converts an empty subtree [] to FALSE'''
      trace('enter convert_empty_subtrees')
      dbg('input tree: ' + str(tree))
      out_tree = []
      for subtree in tree:
         dbg('subtree: ' + str(subtree))
         if isinstance(subtree, list):
            if subtree == []:
               # Replace an empty subtree with FALSE
               dbg('Replacing empty subtree')
               out_tree.append((SCAN_TYPES['NAME'], 'FALSE', -1))
            else:
               out_tree.append(self.convert_empty_subtrees(subtree))
         else:
            out_tree.append(subtree)
      dbg('output tree: ' + str(out_tree))
      trace('leave convert_empty_subtrees')
      return out_tree
   def strip_controls(self, tree):
      '''Strips and handles control sequences'''
      trace('enter strip_controls')
      dbg('input tree is: %s' % str(tree))
      # Handle constant defines: we know these will be at the top level,
      # so non-recursive
      out_tree = []
      for statement in tree:
         op = statement[0]
         dbg('operator token is: %s' % str(op))
         if op[0] == SCAN_TYPES['CTRL']:
            self.control_handler.handle_control(statement)
         else:
            out_tree.append(statement)
      dbg('control-stripped tree is: %s' % str(out_tree))
      trace('leave strip_controls')
      return out_tree
   def check(self):
      '''Main type-checker method'''
      trace('enter check')
      tree, eof = self.parser.parse()
      dbg('parser returned EOF? %s' % str(eof))
      converted = self.convert_empty_subtrees(tree)
      stripped = self.strip_controls(converted)
      for statement in stripped:
         dbg('type-checking top-level statement: %s' % str(statement))
         self.check_statement(statement, True)
      trace('leave check')
      #
      # Return a tuple: (stripped tree, boolean indicating EOF)
      return (stripped, eof)
   def getStackLimit(self):
      return self.stack.getMaxSize()
#


if __name__ == '__main__':
   import traceback
   from parser import Parser
   from treeprinter import print_tree
   from symbol_table import SymbolTable
   from shared_config import PRELOADED_SYMBOLS
   
   p = None
   st = SymbolTable(PRELOADED_SYMBOLS)
   filename = '<stdin>'
   
   if len(sys.argv) > 1:
      filename = sys.argv[1]
      fh = open(filename, 'r')
      p = Parser(fh)
   else:
      print '* Simple LISP Dialect for Teaching :: Type-Checker Component *'
      print ''
      print 'The type-checker is running in interactive mode. To exit, type'
      print 'CTRL+D (CTRL+Z on Windows) to send the EOF character.'
      print ''
      p = Parser(sys.stdin)
   
   type_checker = TypeChecker(p, st)
   eof = False
   code = 0
   
   while not eof:
      try:
         tree, eof = type_checker.check()
         if not (tree == [] and eof):     # suppress spurious print
            print_tree(tree)
            print '==> valid SLDT expression'
            print ''
      except KeyboardInterrupt:
         print 'Exiting on signal 2'
         sys.exit(-2)
      except CompilerException, e:
         print filename + ':' + str(e.line) + ': ' + e.message
         code = 3
      except Exception:
         traceback.print_exc()
         code = 3
   #

   sys.exit(code)
#
